#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
using ll = long long;
const ll N = 6e6 + 10;
ll is_preme[N] = {0}, pri[N] = {0}, cnt, pre[N] = {0};
void init()
{
    for (ll i = 2; i <= N; i++)
    {
        if (cnt == 400001)
            break;
        if (!pri[i])
        {
            is_preme[cnt++] = i;
            if (cnt == 400001)
                break;
        }

        for (ll j = 0; j < cnt && is_preme[j] * i < N; j++)
        {
            pri[i * is_preme[j]] = 1;
            if (i % is_preme[j] == 0)
                break;
        }
    }
}

void solve()
{

    // for (int i = 0; i <= 100;i++)
    // {
    //     cout << is_preme[i] << endl;
    // }
    

    ll n;
    ll sum = 0;
    cin >> n;
    vector<ll> a(n + 1);
    for (ll i = 0; i < n; i++)
    {
        cin >> a[i];
        sum += a[i];
    }

    // cout << sum << ":" << pre[n] << endl;
    if (sum >= pre[n - 1])
    {
        cout << 0 << endl;
    }
    // else {
    //     cout << "sss" << endl;
    // }
    else
    {
        sort(a.begin(), a.end());
        ll ans = 0;

        for (ll i = 0; i < n && i <= cnt; i++)
        {
            sum -= a[i];
            if (sum >= pre[n - i - 1])
            {
                cout << i << endl;
                return;
            }
        }
    }
}
int main()
{
    init();
    for (int i = 0; i < cnt; i++)
    {
        if (i == 0)
        {
            pre[0] = is_preme[0];
            // cout << pre[i] << endl;
            continue;
        }
        pre[i] = pre[i - 1] + is_preme[i];
        // cout << pre[i] << endl;
    }
    // for (int i = 0; i < 100; i++)
    // {
    //     cout << is_preme[i] << endl;
    // }
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}
